给定一个长度为 n 的数组，请你编写一个函数，返回该数组按升序排序后的结果。
数据范围： 
，数组中每个元素都满足 
要求：时间复杂度 )
，空间复杂度 )
进阶：时间复杂度 )
，空间复杂度
注：本题数据范围允许绝大部分排序算法，请尝试多种排序算法的实现。
[编程题]排序
按照标准快速排序的前后指针法，即选取最左侧元素为基准，用一个pre指针和 cur指针均指向起始位置，依次移动cur指针向右遍历。若arr[cur]的值大于等于base，右移cur；若小于base，则向右移pre，并将pre移动后所指的元素与cur所指的进行交换，交换后cur所指的元素必定是大于等于base的值，所以还需右移cur。最后，再交换base与pre所指的元素。
双指针的原理是，确保从左至pre均为小于base的值，从pre到cur所指的均为大于等于base的值。
编写代码如下：
"6/8 组用例通过
class Solution: def partition(self, arr, l, r) -> int: base = arr[l] pre = l cur = l + 1 while cur <= r: if arr[cur] < base: pre += 1 arr[pre], arr[cur] = arr[cur], arr[pre] cur += 1 arr[l], arr[pre] = arr[pre], arr[l] return pre def inner_sort(self, arr, l, r): if l >= r: return arr mid = self.partition(arr, l, r) self.inner_sort(arr, l, mid - 1) self.inner_sort(arr, mid + 1, r) return arr def MySort(self , arr: List[int]) -> List[int]: # write code here return self.inner_sort(arr, 0, len(arr) - 1)由于是递归调用，最终不能通过：
"6/8 组用例通过
RecursionError: maximum recursion depth exceeded in comparison"
改动“inner_sort”函数，借用一个队列，将递归调用改成循环的方式：
def inner_sort(self, arr, l, r): if l >= r: return arr tasks = [(l, r)] while tasks: s, e = tasks.pop(0) if s >= e: continue mid = self.partition(arr, s, e) tasks.append((s, mid - 1)) tasks.append((mid + 1, e)) return arr运行通过。
发表于 2022-07-30 10:30:10
回复(0)
python:
class Solution:
def MySort(self , arr: List[int]) -> List[int]:
# write code here
new_arr = []
for i in range(len(arr)):
new_arr.append(min(arr))
arr.remove(min(arr))
return new_arr
def MySort(self , arr: List[int]) -> List[int]:
# write code here
new_arr = []
for i in range(len(arr)):
new_arr.append(min(arr))
arr.remove(min(arr))
return new_arr
发表于 2022-07-05 11:01:47
回复(0)
class Solution:
def MySort(self , arr: List[int]) -> List[int]:
# write code here
if len(arr) == 1 or len(arr) == 0:
return arr
for i in range(len(arr)-1):
exchange = False
for j in range(len(arr)-1-i):
if arr[j] > arr[j+1]:
arr[j],arr[j+1] = arr[j+1],arr[j]
exchange = True
if not exchange:
def MySort(self , arr: List[int]) -> List[int]:
# write code here
if len(arr) == 1 or len(arr) == 0:
return arr
for i in range(len(arr)-1):
exchange = False
for j in range(len(arr)-1-i):
if arr[j] > arr[j+1]:
arr[j],arr[j+1] = arr[j+1],arr[j]
exchange = True
if not exchange:
return arr
# 不知道为什么最后一个用例通过不了
发表于 2022-05-30 16:55:30
回复(0)
python递归排序，直接通过，冒泡超时 class Solution: def MySort(self , arr: List[int]) -> List[int]: # write code here l1 = [] if len(arr) > 0: for i in range(len(arr)): mins = min(arr) l1.append(mins) arr.remove(mins) self.MySort(arr) return l1
发表于 2022-05-18 12:03:08
回复(0)
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # 将给定数组排序 # @param arr int整型一维数组 待排序的数组 # @return int整型一维数组 # class Solution: # 冒泡排序 # def MySort(self,arr): # for i in range(len(arr) - 1): # for j in range(len(arr) - 1 - i): # if arr[j] > arr[j + 1]: # arr[j],arr[j+1] = arr[j+1],arr[j] # return arr # 选择排序 # def MySort(self,arr): # for i in range(len(arr) - 1): # min_index = i # for j in range(i+1,len(arr)): # if arr[j] < arr[min_index]: # min_index = j # arr[i],arr[min_index] = arr[min_index],arr[i] # return arr # 插入排序 # def MySort(self,arr): # for i in range(1,len(arr)): # key = arr[i] # j = i - 1 # while j >= 0: # if arr[j] > key: # arr[j+1] = arr[j] # arr[j] = key # j -= 1 # return arr # 直接使用sorted排序 # def MySort(self , arr ): # # write code here # return sorted(arr)
发表于 2022-04-18 08:15:29
回复(0)
``` python
class Solution:
def MySort(self , arr: List[int]) -> List[int]:
# write code here
# quick sort
if not arr or len(arr) == 1:
return arr
# self.quick_sort_v2(arr, 0, len(arr) - 1)
self.quick_sort(arr, 0, len(arr) - 1)
return arr
# 双指针, 把比p小的都放到左边
def quick_sort(self, arr, start, end):
if end - start <= 0:
return
mid = int((start + end) / 2)
arr[mid], arr[end] = arr[end], arr[mid]
p = arr[end]
i = start
for j in range(start, end):
if arr[j] < p:
arr[i], arr[j] = arr[j], arr[i]
i+=1
arr[i], arr[end] = arr[end], arr[i]
self.quick_sort(arr, start, i - 1)
self.quick_sort(arr, i + 1, end)
return
发表于 2022-02-27 22:38:39
回复(0)
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 将给定数组排序 # @param arr int整型一维数组 待排序的数组 # @return int整型一维数组 # class Solution: def MySort(self , arr: List[int]) -> List[int]: # write code here def selectSort(arr): #选择排序，175ms，5100KB k = len(arr) temp = -1 index = 0 while k > 0: for i in range(0,k): if arr[i] > temp: temp,index = arr[i],i i += 1 arr[k-1],arr[index] = arr[index],arr[k-1] return arr def bubbleSort(arr): #冒泡排序，186ms，5100KB k = len(arr) while k > 0: for i in range(0,k-1): if arr[i] > arr[i+1]: arr[i],arr[i+1] = arr[i+1],arr[i] i += 1 k -= 1 return arr def insertSort(arr): #插入排序，77ms，5048KB res = [arr[0]] for i in arr[1:]: lenr = len(res)-1 if i <= res[0]: res.insert(0,i) continue while lenr >= 0: if res[lenr] > i: lenr -= 1 else: res.insert(lenr+1,i) break return res def mergeSort(arr): #归并排序，53ms，5040KB if len(arr) < 2: return arr mid = (len(arr))//2 left = mergeSort(arr[:mid]) right = mergeSort(arr[mid:]) i = j =0 res = [] while i<len(left) and j<len(right): if left[i] <= right[j]: res.append(left[i]) i += 1 else: res.append(right[j]) j += 1 if i == len(left):return res + right[j:] else:return res + left[i:] def quickSort(arr): #快速排序，53ms，4984KB list_equal = [] if len(arr) < 2: return arr left,right = 0,len(arr)-1 mid = (left+right)//2 list_left = [] list_right = [] for i in arr: if i > arr[mid]: list_right.append(i) elif i == arr[mid]: list_equal.append(i) else:list_left.append(i) return quickSort(list_left) +list_equal+ quickSort(list_right) return bubbleSort(arr)
发表于 2022-02-22 14:54:19
回复(0)
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 将给定数组排序
# @param arr int整型一维数组 待排序的数组
# @return int整型一维数组
#
class Solution:
def MySort(self , arr: List[int]) -> List[int]:
if len(arr) >=2:
mid=arr[0]
left,right= [],[]
arr.remove(mid)
for num in arr:
if num >=mid:
right.append(num)
else:
left.append(num)
return self.MySort(left) +[mid]+self.MySort(right)
else:
return arr
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 将给定数组排序
# @param arr int整型一维数组 待排序的数组
# @return int整型一维数组
#
class Solution:
def MySort(self , arr: List[int]) -> List[int]:
if len(arr) >=2:
mid=arr[0]
left,right= [],[]
arr.remove(mid)
for num in arr:
if num >=mid:
right.append(num)
else:
left.append(num)
return self.MySort(left) +[mid]+self.MySort(right)
else:
return arr
发表于 2021-12-18 01:02:49
回复(0)
class Solution: def MySort(self , arr: List[int]) -> List[int]: # write code here #桶排序 45% 16% max_value=max(arr) rounds=0 while max_value>=10**rounds: rounds+=1 for i in range(rounds): buckets=[[] for _ in range(10)] for num in arr: location=int((num/10**i)%10) buckets[location].append(num) new=[] for b in range(10): for v in buckets[b]: new.append(v) arr=new return arr #希尔排序 #插入排序 超时 # for i in range(len(arr)): # while i>=1: # if arr[i]<arr[i-1]: # arr[i],arr[i-1]=arr[i-1],arr[i] # i-=1 # return arr #归并排序 成功 15% 20% # def sort_al(lists): # if len(lists)<=1: # return lists # n=len(lists)//2 # res=[] # left=sort_al(lists[0:n]) # right=sort_al(lists[n:]) # while len(left)>0 and len(right)>0: # if left[0]<right[0]: # res.append(left.pop(0)) # else: # res.append(right.pop(0)) # if len(left)>0: # res.extend(left) # else: # res.extend(right) # return res # return sort_al(arr) #冒泡排序 超时 # for i in range(len(arr)): # for j in range(len(arr)-i-1): # if arr[j]>arr[j+1]: # arr[j],arr[j+1]=arr[j+1],arr[j] # return arr # #选择排序超时 # for i in range(len(arr)): # for j in range(i+1,len(arr)): # if arr[i]>arr[j]: # arr[i],arr[j]=arr[j],arr[i] # return arr #快排超时 # def fast_sort(lists,i,j): # if i>j: # return lists # else: # povit=lists[i] # low=i # high=j # while i<j: # while i<j and lists[j]>povit: # j-=1 # lists[i],lists[j]=lists[j],lists[i] # while i<j and lists[i]<povit: # i+=1 # lists[i],lists[j]=lists[j],lists[i] # fast_sort(lists, low, i-1) # fast_sort(lists, i+1, high) # return lists # a=fast_sort(arr, 0, len(arr)-1) # return a
发表于 2021-12-14 05:24:06
回复(0)
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 将给定数组排序 # @param arr int整型一维数组 待排序的数组 # @return int整型一维数组 # class Solution: def MySort(self , arr: List[int]) -> List[int]: # write code here # 开始使用了冒泡，自测通过，但是提交时的用例提示运行超时，就转了下数据类型 # n = len(arr) # for i in range(n): # for j in range(n-i-1): # if arr[j] > arr[j+1]: # arr[j], arr[j+1] = arr[j+1], arr[j] arr = list(arr) arr.sort() return arr
发表于 2021-12-05 15:56:24
回复(0)
class Solution: def MySort(self , arr: List[int]) -> List[int]: # write code here def qs(arr): if len(arr)<=1: return arr else: return qs([a for a in arr[1:] if a<=arr[0]])+[arr[0]]+qs([a for a in arr[1:] if a>arr[0]]) res=qs(arr) return res
发表于 2021-11-26 23:32:56
回复(0)
''' 原理:1. 选取一个元素作为基准值,习惯上选择第一个元素 2.将剩下的元素和基准值比较,小于基准值的放在基准值左边,大于基准值的放在基准值右边 3. 重复1,2步骤,一直到剩最后一个元素 ''' def quick_sort(data:list)->list: if data==[]: return data base = data[0] left = quick_sort([l for l in data[1:] if l<base]) right = quick_sort([r for r in data[1:] if r>=base]) return left+[base]+right ''' 代码解读: 1. 首先data列表传进来 2.递归结束条件,递归传进来的data为空,结束递归.意思是当取最后一个元素当做基准值之后, left=[],right=[],也就是base左边和右边都 没有元素了 3.选取基准值 4.基准值左边排序 5.基准值右边排序 6.返回left+[base]+right '''
发表于 2021-11-10 00:16:48
回复(0)
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 将给定数组排序
# @param arr int整型一维数组 待排序的数组
# @return int整型一维数组
#
class Solution:
def MySort(self , arr ):
# write code here
# quick_sort
def partition(arr, left, right): # 接收列表
tmp = arr[left] # 取出第一个元素
while left < right: # 当两个指针相等退出循环
while left < right and arr[right] >= tmp: # 左边被取出一个元素，从右边开始查找,查找比tmp小的数
right -= 1 # 往左走一步
arr[left] = arr[right] # 从右边找到了，把右边的值写到左边
while left < right and arr[left] <= tmp: # 从左边找比tmp大的数
left += 1
arr[right] = arr[left] # 把左边的值写到右边的空位上
arr[left] = tmp # 跳出大循环时为li[left]=li[right]，令li[left] = tmp
return left
def quick_sort(arr, left, right):
if left < right: # 至少两个元素
mid = partition(arr, left, right)
quick_sort(arr, left, mid-1)
quick_sort(arr, mid+1, right)
quick_sort(arr, 0, len(arr)-1)
return arr
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 将给定数组排序
# @param arr int整型一维数组 待排序的数组
# @return int整型一维数组
#
class Solution:
def MySort(self , arr ):
# write code here
# quick_sort
def partition(arr, left, right): # 接收列表
tmp = arr[left] # 取出第一个元素
while left < right: # 当两个指针相等退出循环
while left < right and arr[right] >= tmp: # 左边被取出一个元素，从右边开始查找,查找比tmp小的数
right -= 1 # 往左走一步
arr[left] = arr[right] # 从右边找到了，把右边的值写到左边
while left < right and arr[left] <= tmp: # 从左边找比tmp大的数
left += 1
arr[right] = arr[left] # 把左边的值写到右边的空位上
arr[left] = tmp # 跳出大循环时为li[left]=li[right]，令li[left] = tmp
return left
def quick_sort(arr, left, right):
if left < right: # 至少两个元素
mid = partition(arr, left, right)
quick_sort(arr, left, mid-1)
quick_sort(arr, mid+1, right)
quick_sort(arr, 0, len(arr)-1)
return arr
发表于 2021-09-14 16:23:01
回复(0)
问题信息
难度：
28条回答
997收藏
13159浏览
通过挑战的用户
查看代码-
2023-03-12 20:16:31
-
2023-03-10 16:50:57 -
2023-03-08 01:29:53 -
2023-02-26 20:40:50 -
2023-02-24 11:16:30
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
